#include "base.h"

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *create_list_from_vec(vector<int> vec)
{
    ListNode *list = nullptr, *list_bak = nullptr;
    for (auto i : vec)
    {
        if (list)
        {
            list->next = new ListNode(i);
            list = list->next;
        }
        else
        {
            list_bak = list = new ListNode(i);
        }
    }
    return list_bak;
}

void ListNode_print(ListNode *node)
{
    while (node)
    {
        printf("%d ", node->val);
        node = node->next;
    }
}

class Solution
{
public:
    int len_of_list(ListNode *node)
    {
        auto len = 0;
        while (node)
        {
            len++;
            node = node->next;
        }
        return len;
    }
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        auto len1 = len_of_list(l1);
        auto len2 = len_of_list(l2);
        //让l1为长的
        if (len2 > len1)
        {
            swap(l1, l2);
        }
        auto l1_bak = l1;
        int jw = 0;
        while (l2)
        {
            l1->val += l2->val + jw;
            jw = 0;
            if (l1->val >= 10)
            {
                jw = 1;
                l1->val %= 10;
            }
            l2 = l2->next;
            if (l2)
            {
                l1 = l1->next;
            }
        }
        auto l1_pre = l1;
        l1 = l1->next;

        while (jw != 0)
        { //最后还有进位
            jw = 0;
            if (l1)
            { //节点存在,
                l1->val += 1;
                if (l1->val >= 10)
                {
                    jw = 1;
                    l1->val %= 10;
                }
                l1_pre = l1_pre->next;
                l1 = l1->next;
            }
            else
            { //节点不存在,创建,进位为1
                l1_pre->next = new ListNode(1);
                l1 = l1_pre->next;
            }
        }
        return l1_bak;
    }
};

void main()
{
    vector<int> nums1 = {9, 9, 9, 9,
                         9, 9, 9};
    vector<int> nums2 = {9, 9, 9, 9};
    auto l1 = create_list_from_vec(nums1);
    auto l2 = create_list_from_vec(nums2);
    Solution sol;
    auto l3 = sol.addTwoNumbers(l1, l2);

    ListNode_print(l3);
}